package com.banmao.CarlCamp.Day03;

/**
 * https://leetcode.cn/problems/design-linked-list/
 */
public class LC707 {

    static class MyLinkedList {

        static class Node {
            int val;
            Node next;
            Node (int val, Node next) {
                this.val = val;
                this.next = next;
            }
        }

        Node dummyHead;
        int size;

        public MyLinkedList() {
            dummyHead = new Node(-1, null);
            size = 0;
        }

        private Node getNode(int index) {
            if (index == -1) {
                return dummyHead;
            }
            if (index < 0 || index >= size) {
                return null;
            }
            Node cur = dummyHead.next;
            int i = 0;
            while (cur != null) {
                if (i == index) {
                    break;
                }
                i++;
                cur = cur.next;
            }
            return cur;
        }

        public int get(int index) {
            Node node = getNode(index);
            return node == null ? -1 : node.val;
        }

        public void addAtHead(int val) {
            Node newNode = new Node(val, dummyHead.next);
            dummyHead.next = newNode;
            size++;
        }

        public void addAtTail(int val) {
            Node newNode = new Node(val, null);
            Node cur = dummyHead;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
            size++;
        }

        public void addAtIndex(int index, int val) {
            Node node = getNode(index - 1);
            if (node != null) {
                Node newNode = new Node(val, node.next);
                node.next = newNode;
                size++;
            }
        }

        public void deleteAtIndex(int index) {
            Node preNode = index == 0 ? dummyHead : getNode(index - 1);
            if (preNode != null) {
                Node delNode = getNode(index);
                if (delNode == null) {
                    preNode.next = null;
                } else {
                    preNode.next = delNode.next;
                    size--;
                }
            }
        }
    }

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addAtHead(4);
        list.get(1);
        list.addAtHead(1);
        list.addAtHead(5);
        list.deleteAtIndex(3);
        list.addAtHead(7);
        list.get(3);
        list.get(3);
        list.get(3);
        list.addAtHead(1);
        list.deleteAtIndex(4);
    }
}
